package com.test.daily.leetcode.y2021.m10.day1026;

import java.util.*;

/**
 * @descriptions: nextGreaterElement
 * @author: Tom
 * @date: 2021/10/26 下午 03:23
 * @version: 1.0
 */
public class Code01_NextGreaterElement {
    public static void main(String[] args) {
        Code01_NextGreaterElement cn = new Code01_NextGreaterElement();
        int[] nums1 = new int[]{4,1,2};
        int[] nums2 = new int[]{1,2,3,4};
        int[] ans = cn.nextGreaterElement1(nums1, nums2);
        for(int member: ans){
            System.out.print(member + " ");
        }
    }

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int N = nums2.length;
        Stack<Integer> stack = new Stack<>();
        for (int i = N - 1; i >= 0; i--) {
            while(!stack.isEmpty() && nums2[stack.peek()] < nums2[i]){
                stack.pop();
            }
            map.put(nums2[i], stack.isEmpty()? -1: nums2[stack.peek()]);
            stack.add(i);
        }
        int ans[] = new int[nums1.length];
        for(int i = 0; i < nums1.length; i++){
            ans[i] = map.get(nums1[i]);
        }
        return ans;
    }

    public int[] nextGreaterElement1(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = nums2.length - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}
